import random
import math


# 加载Iris数据集
def load_iris_data(filename):
    data = []
    labels = []
    class_map = {'Iris-setosa': 0, 'Iris-versicolor': 1, 'Iris-virginica': 2}
    with open(filename, 'r') as f:
        for line in f:
            line = line.strip()
            if not line:
                continue
            parts = line.split(',')
            features = [float(p) for p in parts[:4]]  # 4个特征
            label = class_map[parts[4]]  # 类别映射为0,1,2
            data.append(features)
            labels.append(label)
    return data, labels


# 归一化特征（将特征缩放到[0,1]范围）
def normalize(data):
    min_vals = [min(col) for col in zip(*data)]
    max_vals = [max(col) for col in zip(*data)]
    normalized_data = []
    for row in data:
        normalized = [(row[i] - min_vals[i]) / (max_vals[i] - min_vals[i])
                      if (max_vals[i] - min_vals[i]) != 0 else 0
                      for i in range(len(row))]
        normalized_data.append(normalized)
    return normalized_data


# 划分训练集和测试集（8:2）
def split_train_test(data, labels, test_size=0.2):
    random.seed(42)
    combined = list(zip(data, labels))
    random.shuffle(combined)
    data_shuffled, labels_shuffled = zip(*combined)
    split_idx = int(len(data) * (1 - test_size))
    return (list(data_shuffled[:split_idx]), list(labels_shuffled[:split_idx]),
            list(data_shuffled[split_idx:]), list(labels_shuffled[split_idx:]))


# 计算欧氏距离
def euclidean_distance(x1, x2):
    distance = 0.0
    for i in range(len(x1)):
        distance += (x1[i] - x2[i]) ** 2
    return math.sqrt(distance)


# KNN预测
def knn_predict(train_data, train_labels, test_sample, k):
    # 计算与所有训练样本的距离
    distances = [(euclidean_distance(test_sample, train_sample), label)
                 for train_sample, label in zip(train_data, train_labels)]
    # 按距离排序，取前k个
    distances.sort()
    neighbors = distances[:k]
    # 投票决定类别
    class_counts = {}
    for _, label in neighbors:
        class_counts[label] = class_counts.get(label, 0) + 1
    return max(class_counts, key=class_counts.get)


# 计算准确率
def calculate_accuracy(predictions, true_labels):
    correct = sum(p == t for p, t in zip(predictions, true_labels))
    return correct / len(predictions)


# 主函数
def main():
    data, labels = load_iris_data('iris.data')
    normalized_data = normalize(data)
    train_data, train_labels, test_data, test_labels = split_train_test(normalized_data, labels)

    # 测试不同k值的效果
    for k in [1, 3, 5, 7, 9]:
        predictions = [knn_predict(train_data, train_labels, sample, k) for sample in test_data]
        accuracy = calculate_accuracy(predictions, test_labels)
        print(f"k={k}时，测试集准确率：{accuracy:.4f}")
        wrong_idx = [i for i, (p, t) in enumerate(zip(predictions, test_labels)) if p != t]
        wrong_classes = [(predictions[i], test_labels[i]) for i in wrong_idx]
        print(f"k={k}时，错误样本（预测值, 真实值）：{wrong_classes}")


if __name__ == "__main__":
    main()